/**
 * 0059
 *
 * @Author : Ruoyu Wang
 * @DateTime : 2024/8/12 21:51
 */

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};

        int i = 0, j = 0, k = 0, x = 1;

        while (x <= n * n) {
            res[i][j] = x++;
            i += dx[k % 4];
            j += dy[k % 4];
            if (i >= 0 && i < n && j >= 0 && j < n && res[i][j] == 0) continue;
            i -= dx[k % 4];
            j -= dy[k % 4];
            k++;
            i += dx[k % 4];
            j += dy[k % 4];
        }

        return res;
    }
};

int main() {
    Solution sl;
    sl.generateMatrix(4);
    return 0;
}